#include "algo_compet.h"

vector<bool> digit_(10);

bool digit_test(int num,int type){
	int count = 0;

	if (type == 0)
		digit_.assign(10,0);
//	cout<<num<<endl;
	for (int i = 0; i < 5; ++i){
		int item = num/pow(10,i);
		item = item%10;
		digit_[item] = true;
	}
//	for (int i = 0; i < 10; ++i)
//		cout<<digit_[i]<<" ";
//	cout<<endl;

	for (int i = 0; i < 10; ++i)
		if (digit_[i])
			++count;
	if ((type == 0 && count < 5) || (type == 1 && count < 10))
		return false;
	else 
		return true;
}
//==================================================
void pro_7_1_1(){
	int n;
	int b;
	cout<<"enter the number : ";
	cin>>n;

	for (b = 1234; b <= 98765; ++b){
//			cout<<b<<endl;
//			system("pause");
		if (digit_test(b,0)){
//			cout<<"b inner:"<<b<<endl;
			int a = b * n;
			if (a < 1000 || a > 99999)
				continue;
			else if (!digit_test(a,1))
				continue;
			else 
				cout<<"a = "<<a<<" b = "<<b<<" a/b = "<<a/b<<" n = "<<n<<endl;
		}
	}
}
//================================================== 
void pro_7_1_2(){
	while (true){
		long long max = 0;
		cout<<"enter the n: ";
		int n;
		long long result = 1;
		cin>>n;

		cout<<endl;

		cout<<"enter elements: ";
		int* a = new int[n];
		for (int i = 0; i < n; ++i)
			cin>>a[i];

		for (int i = 0; i < n; ++i){
			for (int j = i; j < n; ++j){
				for (int k = i; k <= j; ++k)
					result *= a[k];

				if (result > max){ 
					max = result;
				}
				result = 1;
			}
		}

		if (max < 0)
			cout<<"-1"<<endl;
		else
			cout<<"max is: "<<max<<endl;

		delete [] a;
	}
}

void pro_7_1_3(){
	int k;
	int y;
	float x;


	cout<<"enter the number k: ";
	cin>>k;
	cout<<endl;

	for (y = k + 1; y <= 2 * k; ++y){
		x = k * y /(y - k);
		if ((x - static_cast<int>(x)) == 0)
			cout<<"1/"<<k<<"= 1/"<<x<<" + 1/"<<y<<endl;
	}
}

bool is_huiwen(int num, int base){
	int num_loc[30];
	int i = 0;
	for (; num != 0; ++i){
		num_loc[i] = num % base;
		num = num / base;
	}
	for (int j = 0; j < i / 2; ++j){
		if (num_loc[j] != num_loc[i - j - 1])
			return false;
	}
	return true;
}

bool is_d_huiwen(int num){
	int count = 0;
	for (int base = 2; base <= 10; ++base){
		if (is_huiwen(num,base))
			count++;
		if (count == 2)
			break;
	} 	
	if (count == 2)
		return true;
	else 
		return false;
}

void pro_7_1_4(){
	int n;
	cout<<"enter the number n: ";
	cin>>n;

	for (++n;;++n){
		if (is_d_huiwen(n)){
			cout<<"n is :"<<n;
			return;
		}
	}
}

void print_permutation(int n, int* A, int cur, int& count){
	if (cur == n){
		cout<<"result  " << ++count << ": ";
		for (int i = 0; i < n; ++i){
			cout<<A[i]<<"  ";
		}
		cout<<endl;
	}
	else {
		for (int i = 1; i <= n; ++i){
			int ok = 1;
			for (int j = 0; j < cur; ++j){
				if (A[j] == i)
					ok = 0;
			}
			if (ok == 1){
				A[cur] = i;
				print_permutation(n,A,cur+1, count);
			}
		}
	}
}

void pro_7_2_1(){
	int n;
	cout<<"enter the number: ";
	cin>>n;

	int* A = new int[n];
	int count=0;
	print_permutation(n,A,0, count);
	count = 0;
	print_permutation(n,A,0, count);
	delete [] A;
}

//void print_subset(int n, int* A, int cur,int* P){
//	cout << "cur=" << cur << ": ";
//	for (int i = 0; i < cur; ++i)
//		cout<<A[i]<<" ";
//	cout<<endl;
//	for (int i = cur; i < n; ++i){
//		int ok = 1;
//		for (int j = 0; j < cur; ++j)
//			if(A[j] == P[i]) ok = 0;
//		cout << "i=" << i << ", cur=" << cur << ":" << endl;
//		if (ok){
//		A[cur] = P[i];
//		print_subset(n, A, cur + 1,P);
//		}
//	}
//}

//void pro_7_3_1(){
//	int p[] = {6,7,8,9,5};
//	int B[5];
//	print_subset(5,B,0,p);
//}

void print_subset(int n, int* B,int* P,int cur){
	if (cur == n){
		for (int i = 0; i < cur; ++i)
			if (B[i]) cout<<P[i]<<" ";
		cout<<endl;	
	}
	else {
		B[cur] = 0;
		print_subset(n,B,P,cur+1);
		B[cur] = 1;
		print_subset(n,B,P,cur+1);
	}
}

void pro_7_3_2(){
	int p[] = {6,7,8,9,5};
	int B[5];
	//print_subset(5,B,p,0);
	subset_fanwai(5,0,p,B);

}

void subset_fanwai(int n,int cur,int* P,int * A){
	for (int i = 0; i < cur; ++i)
		cout<<A[i]<<" ";
	cout<<endl;

	for (int i = cur; i < n; ++i){
		A[cur] = P[i]; 
		subset_fanwai(n,cur+1,P,A);
	}
}

void print_subset(int* set_beg, int* set_end, vector<int>& subset,int& count) {
	cout<<"number: "<<count<<" :: ";
	count++;
	copy(subset.begin(), subset.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	for (int* set_cur=set_beg; set_cur<set_end; ++set_cur) {
		subset.push_back(*set_cur);
		print_subset(set_cur+1, set_end, subset,count);
		subset.pop_back();
	}
}

void prof_zhang() {
	int p[] = {6,7,8,9,5};
	vector<int> subset;
	int count = 0;
	print_subset(p, p+sizeof(p)/sizeof(int), subset,count);
}

void chess_print(const vector<int>& path,int n){
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (path[i] == j)
				cout<<"$";
			else 
				cout<<"o";
		}
		cout<<endl;
	}
	cout<<"===================="<<endl;
}
void queen_8(int n, int cur,vector<int>& path){
	if (cur == n){
		chess_print(path,n);
	}

	else {
		for (int i = 0; i < n; ++i){
			int ok = 1;
			for (int j = 0; j < cur; ++j){
				if ((path[j] == i) || (i - cur == path[j] -j) || (i + cur == path[j] + j)){	
					ok = 0;
					break;
				}
			}
			if (ok){
				path[cur] = i;
				queen_8(n, cur + 1, path);
			}
		}
	}
}
void pro_7_4_1(){
	vector<int> vec(8);
	queen_8(8,0,vec);
}

void match_recursion(int circle, int n, int score, vector<int>& path){
	int pivot = score - (circle - path.size());
	if ( pivot >= n && path.size() <= circle){
		for (int i = 0; i < path.size(); ++i)
			cout<<path[i]<<" ";
		cout<<endl;
	}
	else {
		if (path.size() > circle)
			return;
		else {
			static const int scores[] = {3,1,-1};
			for (int i = 0; i < 3; ++i){
				path.push_back(scores[i]);
				match_recursion(circle,n,score + scores[i], path);
				path.pop_back();
			}
		}
	}
}

void match_fanwai(){
	int score = 0;
	vector<int> path;
	 match_recursion(10, 20,0,path);
	//match_recursion_zhang(10, 20, path);
}

void match_recursion_zhang(int circle, int score, vector<int>& path) {
	if (score <= 0) {
		for (int i = 0; i < path.size(); ++i)
			cout<<path[i]<<" ";
		cout<<endl;
	}
	if (score <= 0 || circle == 0) return;

	static const int scores[3] = {3, 1, 0};
	for (int i=0; i<3; ++i) {
		path.push_back(scores[i]);
		match_recursion_zhang(circle-1, score-scores[i], path);
		path.pop_back();
	}
}

bool is_prime(int num){
	double end = sqrt(static_cast<double>(num));
	if (num ==0 || num == 1)
		return false;
	for (int i = 2; i <= end; ++i){
		if (num % i == 0)
			return false;
	}
	return true;
}

void prime_table(int num,vector<bool>& isp){
	isp.assign(2 * num, false);
	for (int i = 2; i <= 2 * num; ++i)
		if(is_prime(i))
			isp[i] = true;
		else
			isp[i] = false;
}

void print_prime_circle(int n, int cur, int* A, vector<bool>& is_visited, const vector<bool>& isp){
	if (cur == n && isp[A[0] + A[n-1]]){
		for (int i = 0; i < n; ++i)
			cout<<A[i]<<" ";
		cout<<endl;
	}
	else {
		for (int i = 2; i <= n; ++i){
			if (!is_visited[i] && isp[i + A[cur - 1]]){
				//cout<<"cur:"<<cur<<"prime:"<<i+A[cur-1]<<endl;
				//system("pause");
				A[cur] = i;
				is_visited[i] = true;
				print_prime_circle(n, cur + 1, A, is_visited, isp);
				is_visited[i] = false;
			}
		}
	}
}

void pro_7_4_2(){
	int n;
	cout<<"enter the number: ";
	cin>>n;

	int *A = new int[n];
	vector<bool> isp;
	vector<bool> is_visited(n,false);
	prime_table(n, isp);
	A[0] = 1;	
	print_prime_circle(n, 1, A, is_visited, isp);
	delete [] A;
}

void test(){
	int a[] = {4,3,2,4,36,22,12,23,43};
	vector<int> vec(a,a+3);
	cout<<vec.size()<<endl;
	make_heap(vec.begin(),vec.end(),greater<int>());
	int end = sizeof(a)/sizeof(int);
	for (int i = 3; i < end; ++i){
		if (a[i] > vec.front()){
			pop_heap(vec.begin(),vec.end(),greater<int>());
			vec.pop_back();
			vec.push_back(a[i]);
			push_heap(vec.begin(),vec.end(),greater<int>());
		}
	}
	sort_heap(vec.begin(),vec.end(),greater<int>());
	copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," "));
	cout<<endl;
}

bool post_order_verify(int* first, int* last){
	if (first == last)
		return false;

	int root = *(last - 1);
	int * index = first;

	//cout<<root<<endl;
	//system("pause");
	for (; index != last; ++index){
		if (*index >= root)
			break;
	}

	int * index_right = index;

	for (; index_right < last - 1; ++index_right){
		if (*index_right < root)
			return false;
	}

	bool left_verify = true;
	if (index > first)
		left_verify = post_order_verify(first,index);

	bool right_verify = true;
	if (index < last - 1)
		right_verify = post_order_verify(index, last - 1);

	return left_verify && right_verify;
}

void six_100(){
	int a[] = {5,7,6,9,11,10,8};
	cout<<post_order_verify(a,a+sizeof(a)/sizeof(int));
}


void pro_7_5_2(){
	vector<int> cap(3);
	vector<bool> is_existed;
	int result;
	//cout<<"cap capacity: ";
	//for (int i = 0; i < 3; ++i)
	//	cin>>cap[i];
	//cout<<"enter result: ";
	//cin>>result;

	cap[0] = 6; cap[1] = 3; cap[2] = 1;
	result = 4;
	int size = (cap[1] + 1) * (cap[2] + 1);
	is_existed.assign(size, false);
	inner_program(cap, result,is_existed);
}

void print_path(status* cur){
	if (cur == NULL)
		return;
	if (cur->from != cur)
		print_path(cur->from);
	cout<<"process:"<<cur->v[0]<<"  "<<cur->v[1]<<"  "<<cur->v[2]<<endl;
	return;
}

void inner_program(const vector<int>& cap,int result,vector<bool>& is_existed){
	queue<status*> q;
	status* begin = NULL;
	status* cur = NULL;
	status* next = NULL;
	int amount = 0; //每次倾倒的量
	int left = 0;
	int right = 0;
	int lhs = 0;
	int rhs = 0;
	int pivot = 0;
	
	begin = new status();

	begin->v[0] = cap[0];
	begin->v[1] = begin->v[2] = 0;
	begin->from = begin;
	q.push(begin);


	while (!q.empty()){
		cur = q.front();
		//cout<<"queue size:"<<q.size()<<endl;
		q.pop();
		if (cur->v[0] == result || cur->v[1] == result
				|| cur->v[2] == result){
			print_path(cur);
			return;
		}

		for (int i = 0; i < 3; ++i){
			for (int j = 0; j < 3; ++j){
				if (i != j){
					pivot = cur->v[i] - (cap[j] - cur->v[j]);  
					if (pivot > 0) //杯子i 中的水容量大于目前杯子j的可容量 
						amount = cap[j] - cur->v[j];
					else
						amount = cur->v[i];
					left = cur->v[i] - amount;
					right = cur->v[j] + amount;

					next = new status();
					for (int k = 0; k < 3; ++k)
						next->v[k] = cur->v[k];
					next->v[i] = left; 
					next->v[j] = right; 

					lhs = next->v[1] * (cap[2] + 1);
					rhs = next->v[2];

					if (!(is_existed[lhs + rhs])){
						next->from  = cur;
						is_existed[lhs + rhs] = true;
						q.push(next);
					}
					else {
						delete next;
					}
				}
			}
		}
	}
}

//???̸??????? ???????ر???
void chess_board(int board_row, int board_col, int target_row, int target_col, int size, vector<int>& board){
	if (size == 1){
		for (int i = 0; i < board.size(); ++i){
			cout<<board[i]<<" ";
			if ( (i+1)%4 == 0)
				cout<<endl;
		}
		cout<<"--------------------------------------------------"<<endl;
	return ;
	} 
	else {
		int index;
		static int dimention = size;
		static int mark = 1; 
		int d = mark++;
		int half_size = size/2;
		if (target_row < board_row + half_size  //left top
				&& target_col < board_col + half_size){
			chess_board(board_row, board_col,target_row, target_col, half_size, board);
		}
		else {
			index = (board_row + half_size - 1) * dimention + board_col + half_size - 1;
			board[index] = d;
			chess_board(board_row, board_col, board_row + half_size - 1, board_col + half_size - 1, half_size, board);
		}

		if (target_row < board_row + half_size  //right top
				&& target_col >= board_col + half_size){
			chess_board(board_row, board_col + half_size, target_row, target_col, half_size, board);
		}
		else {
			index = (board_row + half_size - 1) * dimention + board_col + half_size ;
			board[index] = d;
			chess_board(board_row, board_col + half_size, board_row + half_size - 1, board_col + half_size, half_size, board);
		}

		if (target_row >= board_row + half_size  //left bottom 
				&& target_col < board_col + half_size){
			chess_board(board_row + half_size, board_col,target_row, target_col, half_size, board);
		}
		else {
			index = (board_row + half_size) * dimention + board_col + half_size - 1;
			board[index] = d;
			chess_board(board_row + half_size, board_col, board_row + half_size, board_col + half_size - 1, half_size, board);
		}

		if (target_row >= board_row + half_size  // right bottom
				&& target_col >= board_col + half_size){
			chess_board(board_row + half_size, board_col + half_size, target_row, target_col, half_size, board);
		}
		else {
			index = (board_row + half_size) * dimention + board_col + half_size;
			board[index] = d;
			chess_board(board_row + half_size, board_col + half_size, board_row + half_size, board_col + half_size, half_size, board);
		}
	}
}

void pro_8_3_1(){
	vector<int> v(16); 
	chess_board(0,0,0,0,4,v);
	for (int i = 0; i < v.size(); ++i){
		cout<<v[i]<<" ";
		if ( (i+1)%4 == 0)
			cout<<endl;
	}
}
void test_4_22(){
	while(true){
		for (int i = 0; i < 9400000; ++i);
		Sleep(10);
	}
}

void merge_BStree(Node* lhs, Node* rhs)
{
	if (lhs == NULL || rhs == NULL)
		return;
	if (lhs->left == NULL && lhs->right == NULL)
		insert_node(lhs-value,rhs);
	else{
		if (lhs->value < rhs->value){
			Node* tmp = lhs->right; 
			lhs->right = NULL;
			merge_BStree(lhs, rhs->left);
			merge_BStree(tmp, rhs);
		}
		else if(lhs->value > rhs->value){
			Node* tmp = lhs->left; 
			lhs->left = NULL;
			merge_BStree(tmp,rhs);
			merge_BStree(lhs,rhs->right);
		}
		else 
			throw std::logical_error("exception");
	}
} 

Node* insert_node(int value, Node* head){
	if (head == NULL){
		head = new Node();
		head->value = value;
		head->left = NULL;
		head->right = NULL;
	}
	else if (head->left == NULL && head->right == NULL){
		Node* cur = new Node();
		cur->value = value;
		if (cur->value < head->value)
			head->left = cur;
		else if (cur->value > head->value)
			head->right = cur;
		//equal value needn't to be inserted
	}

	else {
		if (value < head->value)
			insert_node(value, head->left);
		else if (value > head->value)
			insert_node(value, head->right);
	}
	return head;
}

Node* insert_node_zyt(int value, Node* head){
	if (head == NULL){
		head = new Node();
		head->value = value;
		head->left = NULL;
		head->right = NULL;
	}
	else {
		if (value < head->value)
			head->left = insert_node(value, head->left);
		else if (value > head->value)
			head->right = insert_node(value, head->right);
	}
	return head;
}

Node* insert_node_1(int value, Node* head){
	Node* cur = head;
	Node* parent = head;
	while (cur != NULL){
		parent = cur;
		if (value < cur->value)
			cur = cur->left;
		else if (value > cur->value)
			cur = cur->right;
		else
			return;
	}
	if (cur == NULL){
		cur = new Node();
		cur->value = value;
		cur->left = NULL;
		cur->right = NULL;

		if (parent->value < cur->value)
			parent->right = cur;
		else
			parent->left = cur;
	}
	return head;
}
void pre_order_traversal_no_rec(Node* root){
	if (root == NULL)
		return;
	else {
		vector<Node*> s;
		while (s.size() != 0 || root != NULL){
			if (root != NULL){
				cout<<root->value<<endl;
				s.push_back(root);
				root = root->left;
			}
			else{
				root = s.back();
				s.pop_back();
				root = root->right;
			}
		}
	}
}

void in_order_traversal_no_rec(Node* root){
	vector<Node*> s;
	while (s.size() != 0 || root != NULL){
		if (root != NULL){
			s.push_back(root);
			root = root->left;
		}
		else {
			root = s.pop_back();
			cout<<root->value<<endl;
			root = root->right;
		}
	}
	
}



void post_order(Node* root){
	if (root != NULL){
		vector<pair<Node*, bool> > s;
		s.push_back(make_pair(root, false));
		pair<Node*, bool> cur;
		while (s.size() != 0){
			cur = s.back();
			s.pop_back();
			Node* cur_node = cur.first;
			bool is_visited = cur_node.second; 
			if (is_visited == true){
				cout<<cur_node->value<<" ";
			}
			else {
				cur.second = true;
				s.push_back(cur);
				if (cur_node->right != NULL){
					s.push_back(make_pair(cur_node->right, false));
				}
				if (cur_node->left != NULL){
					s.push_back(make_pair(cur_node->left, false));
				}
			}
		}
	}
}


void pre_order(Node* root){
	if (root == NULL)
		return; 
	else {
		vector<Node*> s;
		s.push_back(root);
		Node* cur = NULL;
		while (s.size() != 0){
			cur = s.back();
			s.pop_back();
			cout<<cur->value<<" ";
			if(cur->right != NULL)
				s.push_back(cur->right);
			if(cur->left != NULL) 
				s.push_back(cur->left);
		}
	}
}
void in_order(Node* root){
	if (root == NULL)
		return;
	else {
		vector<Node*> s;
		s.push_back(make_pair(root,false));
		pair<Node*, bool> cur;
		Node* cur_node = NULL;
		bool is_visited = false;
		while (s.size() != 0){
			cur = s.back();
			s.pop_back();
			cur_node = cur.first;
			is_visited = cur.second;
			if (is_visited == true){
				cout<<cur_node->value<<" ";
			}
			else {
				if (cur->right != NULL)
					s.push_back(make_pair(cur_node->right,false));

				s.push_back(make_pair(cur_node, true));

				if(cur->left != NULL) 
					s.push_back(make_pair(cur_node->left, false));
			}
		}
	}
}
